package com.easy;

/**
 * Created by Lxk on 2020/2/1.
 */
public class Solution109 {

    private TreeNode buildBST(ListNode begin) {
        if (begin == null) {
            return null;
        }
        ListNode slower = begin, faster = begin;
        while (faster != null) {
            faster = faster.next;
            if (faster != null) {
                faster = faster.next;
            } else {
                break;
            }
            slower = slower.next;
        }
        TreeNode node = new TreeNode(slower.val);
        ListNode pre = begin;
        if (slower == begin) {
            node.left = buildBST(null);
            node.right = buildBST(null);
        } else {
            while (pre.next != slower) {
                pre = pre.next;
            }
            pre.next = null;
            node.left = buildBST(begin);
            node.right = buildBST(slower.next);
        }
        return node;
    }

    public TreeNode sortedListToBST(ListNode head) {
        return buildBST(head);
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(-10);
        ListNode node2 = new ListNode(-3);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(9);
        node.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        Solution109 solution109 = new Solution109();
        TreeNode root = solution109.sortedListToBST(node);
        System.out.println(root);
    }

}
